import java.util.*;


public class TreeLeetcode {
    public static void main(String[] args) {
//        String str = "abcd";
//        char[] charArray = str.toCharArray();
        //将字符数组反转
//        Arrays.parallelSort(charArray,Collections.reverseOrder());
//        System.out.println(charArray[0]);
//        Integer[] reversedArray = IntStream.of(array).sorted(Comparator.reverseOrder()).toArray(Integer[]::new);
//        Set<Integer> set = new HashSet<>();
//        set.add(1);
//        set.add(2);

//        Integer[] array2 = set.toArray(new Integer[0]);
//        System.out.println(array2);
        int[] array = new int[5];
        Arrays.fill(array,1,5,6);

//        String[] ss = new String[10];
//        Arrays.sort(ss, (a, b) -> {
//            String sa = a + b, sb = b + a ;
//            return sb.compareTo(sa);
//        });
//        Arrays.sort(ss,(a,b)->a.compareTo(b));
//        Arrays.sort(ss, new Comparator<String>() {
//            @Override
//            public int compare(String o1, String o2) {
//                o1.compareTo(o2);
//                return 0;
//            }
//        });
        PriorityQueue<Integer> pq = new PriorityQueue<>(3);
        pq.add(1);
        pq.add(10);
        pq.add(100);
        pq.add(1000);
        System.out.println(pq);
        int size = pq.size();
        //得到优先队列中的最大值
//        int maxRow = pq.poll();
//        System.out.println(maxRow);
        int maxRow = pq.peek();
        pq.remove(maxRow);

//        System.out.println(Arrays.toString(array));
    }
    /**
     * BookMyShow类用于模拟电影票预订系统
     * 它可以跟踪多行座位的预订情况，并支持聚集和分散预订两种方式
     * 聚集预订（gather）是指找到连续的k个座位并预订
     * 分散预订（scatter）是指在多行中找到总共k个座位并预订，不要求座位连续
     */
    class BookMyShow {
        // n表示行数
        private final int n;
        // m表示每行的座位数
        private final int m;
        // minTree是用于存储每行最小座位数的线段树
        private final int[] minTree;
        // sumTree是用于存储每行座位数总和的线段树
        private final long[] sumTree;

        /**
         * 构造方法初始化BookMyShow对象
         * @param n 行数
         * @param m 每行的座位数
         */
        public BookMyShow(int n, int m) {
            this.n = n;
            this.m = m;
            // 初始化线段树数组，大小为行数的4倍
            this.minTree = new int[4 * n];
            this.sumTree = new long[4 * n];
        }

        /**
         * 修改指定索引的座位数
         * @param i 线段树节点索引
         * @param l 线段树节点覆盖的左边界
         * @param r 线段树节点覆盖的右边界
         * @param index 需要修改的座位索引
         * @param val 新的座位数
         */
        private void modify(int i, int l, int r, int index, int val) {
            if (l == r) {
                // 当到达叶子节点时，更新最小和总和线段树
                minTree[i] = val;
                sumTree[i] = val;
                return;
            }
            int mid = (l + r) / 2;
            if (index <= mid) {
                // 如果索引位于左半部分，递归修改左子树
                modify(i * 2, l, mid, index, val);
            } else {
                // 否则，递归修改右子树
                modify(i * 2 + 1, mid + 1, r, index, val);
            }
            // 更新当前节点的最小值和总和值
            minTree[i] = Math.min(minTree[i * 2], minTree[i * 2 + 1]);
            sumTree[i] = sumTree[i * 2] + sumTree[i * 2 + 1];
        }

        /**
         * 查询最小行号，其最小座位数不大于val
         * @param i 线段树节点索引
         * @param l 线段树节点覆盖的左边界
         * @param r 线段树节点覆盖的右边界
         * @param val 座位数的阈值
         * @return 最小行号，如果不存在则返回n
         */
        private int queryMinRow(int i, int l, int r, int val) {
            if (l == r) {
                // 当到达叶子节点时，如果当前行的最小座位数大于val，则返回n，表示不存在这样的行
                if (minTree[i] > val) {
                    return n;
                }
                return l;
            }
            int mid = (l + r) / 2;
            if (minTree[i * 2] <= val) {
                // 如果左子树的最小值不大于val，递归查询左子树
                return queryMinRow(i * 2, l, mid, val);
            } else {
                // 否则，递归查询右子树
                return queryMinRow(i * 2 + 1, mid + 1, r, val);
            }
        }

        /**
         * 查询指定范围内的座位数总和
         * @param i 线段树节点索引
         * @param l 线段树节点覆盖的左边界
         * @param r 线段树节点覆盖的右边界
         * @param l2 查询范围的左边界
         * @param r2 查询范围的右边界
         * @return 指定范围内座位数的总和
         */
        private long querySum(int i, int l, int r, int l2, int r2) {
            if (l2 <= l && r <= r2) {
                // 如果当前节点覆盖的范围完全在查询范围内，直接返回节点的总和值
                return sumTree[i];
            }
            int mid = (l + r) / 2;
            long sum = 0;
            if (mid >= l2) {
                // 如果左半部分有重叠，递归查询左子树
                sum += querySum(i * 2, l, mid, l2, r2);
            }
            if (mid + 1 <= r2) {
                // 如果右半部分有重叠，递归查询右子树
                sum += querySum(i * 2 + 1, mid + 1, r, l2, r2);
            }
            return sum;
        }

        /**
         * 聚集预订方法，找到连续的k个座位并预订
         * @param k 需要预订的座位数
         * @param maxRow 最大行号
         * @return 如果找到合适的座位，返回座位的起始行号和之前使用的座位数；否则返回空数组
         */
        public int[] gather(int k, int maxRow) {
            // 找到最小行号，其最小座位数不大于m-k
            int i = queryMinRow(1, 0, n - 1, m - k);
            if (i > maxRow) {
                // 如果最小行号大于最大行号，表示找不到合适的座位，返回空数组
                return new int[0];
            }
            // 查询并更新使用了多少座位
            long used = querySum(1, 0, n - 1, i, i);
            modify(1, 0, n - 1, i, (int) (used + k));
            return new int[]{i, (int)used};
        }

        /**
         * 分散预订方法，在多行中找到总共k个座位并预订
         * @param k 需要预订的座位数
         * @param maxRow 最大行号
         * @return 如果找到合适的座位，返回true；否则返回false
         */
        public boolean scatter(int k, int maxRow) {
            // 计算当前预订的总座位数
            long usedTotal = querySum(1, 0, n - 1, 0, maxRow);
            if ((maxRow + 1L) * m - usedTotal < k) {
                // 如果剩余座位数不足k个，返回false
                return false;
            }
            // 从最小行号开始，逐步找到并预订座位
            int i = queryMinRow(1, 0, n - 1, m - 1);
            while (true) {
                long used = querySum(1, 0, n - 1, i, i);
                if (m - used >= k) {
                    // 如果当前行剩余座位数足够，更新座位数并结束循环
                    modify(1, 0, n - 1, i, (int) (used + k));
                    break;
                }
                // 如果当前行剩余座位数不足，预订所有剩余座位，并继续查找下一行
                k -= m - used;
                modify(1, 0, n - 1, i, m);
                i++;
            }
            return true;
        }
    }

}
